package 贪心;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @PackageName: 贪心
 * @ClassName: LeetCode1405
 * @Author: chen jinxu
 * @Date: 2022/8/11 22:44
 * @Description: //最长快乐字符串
 * 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
 * 给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
 * s 是一个尽可能长的快乐字符串。
 * s 中 最多 有a 个字母 'a'、b个字母 'b'、c 个字母 'c' 。
 * s 中只含有 'a'、'b' 、'c' 三种字母。
 * 如果不存在这样的字符串 s ，请返回一个空字符串 ""。
 * 输入：a = 1, b = 1, c = 7
 * 输出："ccaccbcc"
 * 解释："ccbccacc" 也是一种正确答案。
 * 输入：a = 2, b = 2, c = 1
 * 输出："aabbc"
 * 输入：a = 7, b = 1, c = 0
 * 输出："aabaa"
 * 解释：这是该测试用例的唯一正确答案。
 */
public class LeetCode1405 {
    public static void main(String[] args) {
        System.out.println(longestDiverseString(1, 1, 7));
        System.out.println(longestDiverseString(2, 2, 1));
        System.out.println(longestDiverseString(7, 1, 0));
        System.out.println("---------------");
        System.out.println(longestDiverseString2(1, 1, 7));
        System.out.println(longestDiverseString2(2, 2, 1));
        System.out.println(longestDiverseString2(7, 1, 0));

    }

    public static String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> q = new PriorityQueue<>((x, y) -> y[1] - x[1]);
        if (a > 0) {
            q.add(new int[]{0, a});
        }
        if (b > 0) {
            q.add(new int[]{1, b});
        }
        if (c > 0) {
            q.add(new int[]{2, c});
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int n = sb.length();
            if (n >= 2 && sb.charAt(n - 1) - 'a' == cur[0] && sb.charAt(n - 2) - 'a' == cur[0]) {
                if (q.isEmpty()) {
                    break;
                }
                int[] next = q.poll();
                sb.append((char) (next[0] + 'a'));
                if (--next[1] != 0) {
                    q.add(next);
                }
                q.add(cur);
            } else {
                sb.append((char) (cur[0] + 'a'));
                if (--cur[1] != 0) {
                    q.add(cur);
                }
            }
        }
        return sb.toString();
    }

    public static String longestDiverseString2(int a, int b, int c) {
        StringBuilder res = new StringBuilder();
        Pair[] arr = new Pair[] {new Pair(a, 'a'), new Pair(b, 'b'), new Pair(c, 'c')};
        while (true) {
            Arrays.sort(arr, (p1, p2) -> p2.frep - p1.frep);
            boolean haveNext = false;
            for (Pair pair : arr) {
                if (pair.frep <= 0) {
                    break;
                }
                int m = res.length();
                if (m >= 2 && res.charAt(m - 2) == pair.ch && res.charAt(m - 1) == pair.ch) {
                    continue;
                }
                haveNext = true;
                res.append(pair.ch);
                pair.frep--;
                break;
            }
            if (!haveNext) {
                break;
            }
        }
        return res.toString();
    }

    static class Pair {
        int frep;
        char ch;

        public Pair(int frep, char ch) {
            this.frep = frep;
            this.ch = ch;
        }
    }

}
